home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 9 / Night Owl CD-ROM (NOPV9) (Night Owl Publisher) (1993).ISO / 009a / snpd0493.zip / HUGESORT.C < prev    next >
Text File  |  1993-04-05  |  2KB  |  87 lines
  1. .I 7 49
  2.       char tmp;
  3.  
  4.       do
  5.       {
  6.             tmp = *a; *a++ = *b; *b++ = tmp;
  7.       } while ( --n );
  8. }
  9. void hugesort(void huge *basep,
  10.               unsigned   nel,
  11.               unsigned   width,
  12.               int      (*comp)(void huge *, void huge *))
  13. {
  14.       char huge *i, huge *j;
  15.       unsigned int lnel, rnel;
  16.       char huge *base = (char huge *)basep;
  17.  
  18.       while (nel > 1)
  19.       {
  20.             swap(base, base + (long)width * (nel / 2), width);
  21.             for (i = base, j = base + (long)width * nel; ; )
  22.             {
  23.                   do
  24.                         j -= width;
  25.                   while ( (*comp)(j, base) > 0 );
  26.                   do
  27.                         i += width;
  28.                   while ( i < j && (*comp)(i, base) < 0 );
  29.                   if (i >= j)
  30.                         break;
  31.                   swap(i, j, width);
  32.             }
  33.             swap(j, base, width);
  34.             lnel = (unsigned)((long)(j - base) / width);
  35.             rnel = nel - lnel - 1;
  36.             j += width;
  37.             if (lnel < rnel)
  38.             {
  39.                   hugesort(base, lnel, width, comp);
  40.                   base = j;
  41.                   nel = rnel;
  42.             }
  43.             else
  44.             {
  45.                   hugesort(j, rnel, width, comp);
  46.                   nel = lnel;
  47.             }
  48.       }
  49. }
  50.  
  51. .D 8 39
  52. .I 47 1
  53.  
  54. .I 61 2
  55.       return ((X huge *)a)->key < ((X huge *)b)->key ? -1 :
  56.             ((X huge *)a)->key > ((X huge *)b)->key ? 1 : 0;
  57. .D 62 2
  58. .I 67 27
  59.       X huge *v;
  60.       int n;
  61.       int i, j;
  62.  
  63.       n = 300;                            /* default element count */
  64.       if (argc > 1)
  65.             n = atoi(argv[1]);
  66.       printf("test with %d elements\n", n);
  67.       v = farmalloc(sizeof(X) * (long)n);
  68.       assert(v);                          /* be sure we got memory */
  69.       for (i = 0; i < n; ++i)             /* random init */
  70.       {
  71.             v[i].key = rand();
  72.             for (j = 0; j < PADSIZE; ++j)
  73.                   v[i].pad[j] = rand();
  74.       }
  75.       for (i = 0; i < n; ++i)             /* display before */
  76.             printf(" %d", v[i].key);
  77.       printf("\n");
  78.       hugesort(v, n, sizeof(X), cmpv);    /* sort it */
  79.       for ( i = 0; i < n; ++i )           /* display after */
  80.             printf(" %d", v[i].key);
  81.       printf("\n");
  82.       return 0;
  83. }
  84.  
  85. #endif
  86. .D 68 26
  87.